package edu.purdue.cs.ds;

import java.util.ArrayList;
import java.util.Collections;

public class ServerSets {

	private int n;
	private int k;
	private int l;
	private ArrayList<ArrayList<Integer>> sets;
	
	public static void main(String[] args){
		
		ServerSets s = new ServerSets(4,2);
		ArrayList<ArrayList<Integer>> set = s.constructServerSets();
		for(int i = 0; i < set.size(); ++i)
			System.out.println(set.get(i).toString());
	}
	
	public ServerSets(int npar, int kpar){
		
		n = npar;
		k = kpar;
		l = getL();
		System.out.println("N: " + n + " K: " + k + " L: " + l);
	}
	
	/**
	 * Returns L, the number of shares
	 */
	public int getL(){
		
		int curr_n = n;
		int curr_k = k;
		int num = 1;
		int denom = 1;
		while(curr_n >= (n-k+1))
			num *= curr_n--;
		
		while(curr_k > 1)
			denom *= curr_k--;
			
		return (num/denom);
	}
	
	public static int getL(int npar, int kpar){
		int curr_n = npar;
		int curr_k = kpar;
		int num = 1;
		int denom = 1;
		while(curr_n >= (npar-kpar+1))
			num *= curr_n--;
		
		while(curr_k > 1)
			denom *= curr_k--;
			
		return (num/denom);
	}
	
	/**
	 * Construct the L Server Sets
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> constructServerSets(){
		
		sets = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i < l; ++i)
			sets.add(new ArrayList<Integer>());
		
		if(k == 1){
			for(int i = 0; i < n; ++i)
				sets.get(i).add(i);
		}else{
			addServers(sets,0,0,0);
		}
		
		for(int i = 0; i < sets.size(); ++i)
			Collections.sort(sets.get(i));
		
		return sets;
	}
	
	public int addServers(ArrayList<ArrayList<Integer>> set, int share, int server, int size){
		
		if(server == n)
			return -1;
		if(size > k-1)
			return -1;
		if(share > l-1 || share < 0)
			return -1;
		
		//for(int i = 0; i < size; ++i) System.out.print("     ");
		//System.out.println("Adding Server " + server + " to share " + share);
		set.get(share).add(server);
		
		if(size == k-1){
			return 1;
		}
		
		int oldpos = share;
		int newpos = share;
		int newserver = server;
		int nextserver = server;
		
		while(newserver <= (n-(k-size))){
			
			int res;
			if(size == 0)
				res = addServers(set,newpos,nextserver+1,size+1);
			else
				res = addServers(set,newpos,++newserver,size+1);
			
			if(res == 1)
				newpos += res;
			else if(res == -1)
				newpos++;
			else
				newpos = res;
			
			nextserver++;
			
			if((size == 0)){
				
				if(newpos >= l)
					break;
				
				//System.out.println("NXTS: " + nextserver + " NEWS: " + newserver + " POS: " + newpos);
				
				if(((nextserver+1) > (n-k+1)) && ((newserver+1) <= (n-(k-size)))){
					//for(int i = 0; i < size; ++i) System.out.print("     ");
					//System.out.println("Increment Server: " + newserver);
					newserver++;
					
					for(int i = oldpos; i < newpos; ++i)
						if(!set.get(i).contains(newserver-1))
							set.get(i).add(newserver-1);
					
					if(!set.get(newpos).contains(newserver))
						set.get(newpos).add(newserver);
					
					oldpos = newpos;
					nextserver = newserver;
					
				}
			}
		}
		
		if(newpos < 0 || newpos == share){
			//for(int i = 0; i < size; ++i) System.out.print("     ");
			//System.out.println("Returning 1");
			return 1;
		}else{
			//for(int i = 0; i < size; ++i) System.out.print("     ");
			//System.out.println("Returning " + newpos);
			
			if(size != 0)
			for(int i = oldpos; i < newpos; ++i)
				if(!set.get(i).contains(server))
					set.get(i).add(server);
			
			return newpos;
		}
		
	}
	
	/**
	 * Returns TRUE when serverID is in shareSet
	 * @param serverID
	 * @param shareSet
	 * @return
	 */
	public boolean inSet(int serverID, int shareSet){
		
		return sets.get(shareSet).contains(serverID);
	}
}
